﻿/**************************************************************
 * Copyright Eastmoney Corporation. All rights reserved.
 * 
 * Author: guitao(guitao@eastmoney.com) 
 * Create Date: 2020/8/10 15:15:53
 * Description:
 *          
 * Revision History:
 *      Date         Author               Description
 *              
***************************************************************/

using System;
using System.Collections.Generic;
using System.Collections.Specialized;
using System.ComponentModel;
using System.Data;
using System.Linq;
using System.Linq.Expressions;
using System.Runtime.InteropServices;
using System.Text;
using System.Text.RegularExpressions;
using System.Threading;
using System.Threading.Tasks;
using Xunit;

namespace Algorithm.Samples
{
    public class StringTest
    {
        public void StringEval_Test()
        {
            var str_foumula_1 = "${guba.fans}*0.7+${guba.follows}*0.3";
            var str_foumula_2 = "${passport.field1}";
            var pattern = @"[$]{(\w*\.[0-9a-zA-Z-]*)}";
            //var s = Regex.Replace(str_foumula_1, pattern,"1")

            var matchCollection_1 = Regex.Matches(str_foumula_1, pattern);
            //var match_1 = Regex.Match(str_foumula_1, pattern);
            var matchCollection_2 = Regex.Matches(str_foumula_2, pattern);

            var match = Regex.Match(str_foumula_1, pattern);
            var temp = str_foumula_1;
            while (match.Success)
            {
                var match_str = match.Value;
                //get source.field value
                var value = "100";
                temp = temp.Replace(match_str, value);
                match = match.NextMatch();
            }
            //Assert.Equal("100*0.3+100*0.7", temp);

            using (DataTable dt = new DataTable())
            {
                var result = dt.Compute(temp, "false").ToString();
                Assert.Equal("100.0", result);
            }
            using (DataTable dt = new DataTable())
            {
                var result = long.Parse(dt.Compute("5556", "false").ToString());
            }
        }


        [Fact]
        public void NameValue_Test()
        {
            var nv = new NameValueCollection();
            nv.Add("key", "value1");
            nv.Add("key", "value2");

            Assert.Equal("value1,value2", nv["key"]);

            nv.Set("key2", "value1");
            Assert.Equal("value1", nv["key2"]);
            nv.Set("key2", "value2");
            Assert.Equal("value2", nv["key2"]);

            var v = string.Format("{0} 123", 23, 23, 4);
        }

        [Fact]
        public void Base_Test()
        {
            long x = (1L << 2) | 3;

            string a = "abc";
            string b = "abc";
            //字符串的留存性，初始化后会放入常量池，b直接引用a的对象
            Assert.True(string.ReferenceEquals(a, b));
            string c = new String("abc");
            string d = new String("abc");

            //运算符 重写了，通过 equals 实现的
            Assert.True(c == d);

            //直接new的话，会重新分配内存
            Assert.False(string.ReferenceEquals(c, d));
            Assert.False(string.ReferenceEquals(a, c));
            string e = "abc";
            //这里e还是使用字符串的留存性，且使用的还是a的地址。证明c分配的内存引用并没有放入常量池替换
            Assert.True(string.ReferenceEquals(a, e));
            Assert.False(string.ReferenceEquals(c, e));

            string f = "abc" + "abc";
            string g = a + b;
            string h = "abcabc";
            //f在编译期间确定，实际还是从常量池中获取
            //IsInterned 表示从常量池中获取对应的字符串，获取失败返回null
            //a+b实际上是发生了字符串组合运算，内部重新new了一个新的字符串，所以f,g引用地址不同
            Assert.False(string.ReferenceEquals(f, g));
            Assert.True(string.ReferenceEquals(string.IsInterned(f), h));
            Assert.True(string.ReferenceEquals(f, h));

            //引用类型参数
            TestClass s = new TestClass();
            s.Tag = "abc";

            TestMethod m = new TestMethod();
            m.ReNew(s);
            //参数s 实际是对象 s的 地址拷贝。两者在栈上不同，但是指向的堆地址相同
            //在ReNew方法中 "参数s" 重新指向了一个新的对象，但是不影响旧的对象s
            Assert.True(string.Equals("abc", s.Tag));

            m.Change(s, "123");
            //Change方法是直接修改 参数s 指向的堆对象内的字段数据，所有对象s字段也发生了变化
            Assert.True(string.Equals("123", s.Tag));

            m.ReNew2(ref s);
            //注意和ReNew的区别，因为是ref 引用传递，所有原对象引用地址指向了新new的对象地址
            Assert.False(string.Equals("abc", s.Tag));
            Assert.True(string.Equals("cba", s.Tag));

            //值类型参数
            int val = 100;
            //Change方法内部改变了val的值，但不影响val原来的值
            m.Change(val);
            Assert.True(val == 100);

            m.Change(out val);
            //使用out标记，改变了val原来的值
            Assert.True(val == 123);
        }

        [Fact]
        public void Should_GetPermutation()
        {
            StringAlgorithm alg = new StringAlgorithm();

            Assert.Equal("213", alg.GetPermutation(3, 3));

            Assert.Equal("132", alg.GetPermutation(3, 2));

            Assert.Equal("4123", alg.GetPermutation(4, 19));
        }
        [Fact]
        public void Should_ReverseParentheses()
        {
            StringAlgorithm alg = new StringAlgorithm();
            Assert.Equal("dcba", alg.ReverseParentheses("(abcd)"));
            Assert.Equal("iloveu", alg.ReverseParentheses("(u(love)i)"));
            Assert.Equal("leetcode", alg.ReverseParentheses("(ed(et(oc))el)"));
            Assert.Equal("apmnolkjihgfedcbq", alg.ReverseParentheses("a(bcdefghijkl(mno)p)q"));
        }
    }

    public class TestMethod
    {
        public void ReNew(TestClass c)
        {
            c = new TestClass() { Tag = "cba" };
        }

        public void ReNew2(ref TestClass c)
        {
            c = new TestClass() { Tag = "cba" };
        }

        public void Change(TestClass c, string tag)
        {
            c.Tag = tag;
        }

        public void Change(int a)
        {
            a = 123;
        }
        public void Change(out int a)
        {
            a = 123;
        }
    }

    public class TestClass
    {
        public string Tag { get; set; }
    }


    /// <summary>
    /// 字符串相关算法
    /// </summary>
    public class StringAlgorithm
    {
        /// <summary>
        /// 求最长有效括号的长度
        /// (()   output:2
        /// )()()) output:4
        /// </summary>
        /// <param name="s"></param>
        /// <returns></returns>
        public int LongestValidParentheses(string s)
        {
            //对于遇到的每个‘(’ ，我们将它的下标放入栈中
            //对于遇到的每个‘)’ ，我们先弹出栈顶元素表示匹配了当前右括号：
            //    如果栈为空，说明当前的右括号为没有被匹配的右括号，我们将其下标放入栈中来更新我们之前提到的「最后一个没有被匹配的右括号的下标」
            //    如果栈不为空，当前右括号的下标减去栈顶元素即为「以该右括号为结尾的最长有效括号的长度」
            int maxns = 0;
            Stack<int> stack = new Stack<int>();
            stack.Push(-1);
            for (int i = 0; i < s.Length; i++)
            {
                if (s.Substring(i, 1) == "(")
                {
                    stack.Push(i);
                }
                else
                {
                    stack.Pop();
                    if (stack.Count == 0)
                    {
                        stack.Push(i);
                    }
                    else
                    {
                        maxns = Math.Max(maxns, i - stack.Peek());
                    }
                }
            }
            return maxns;
        }

        /// <summary>
        /// 设计一种算法，打印n对括号的所有合法的（例如，开闭一一对应）组合。 说明：解集不能包含重复的子集
        /// n=3,  ["((()))","(()())","(())()","()(())","()()()"]
        /// </summary>
        /// <param name="n"></param>
        /// <returns></returns>
        public IList<string> GenerateParenthesis(int n)
        {
            List<string> res = new List<string>();
            if (n == 0) return res;

            dfs("", n, n, res);
            return res;
        }

        /**
         * @param curStr 当前递归得到的结果
         * @param left   左括号还有几个可以使用
         * @param right  右括号还有几个可以使用
         * @param res    结果集
        */
        private void dfs(string curStr, int left, int right, List<string> res)
        {
            // 因为每一次尝试，都使用新的字符串变量，所以无需回溯
            // 在递归终止的时候，直接把它添加到结果集即可，注意与「力扣」第 46 题、第 39 题区分
            if (left == 0 && right == 0)
            {
                res.Add(curStr);
                return;
            }

            // 剪枝（如图，左括号可以使用的个数严格大于右括号可以使用的个数，才剪枝，注意这个细节）
            if (left > right)
            {
                return;
            }

            if (left > 0)
            {
                dfs(curStr + "(", left - 1, right, res);
            }

            if (right > 0)
            {
                dfs(curStr + ")", left, right - 1, res);
            }
        }


        private bool ValidParenthesis(char[] current)
        {
            int balance = 0;
            foreach (var c in current)
            {
                if (c == '(') balance++;
                else balance--;
                if (balance < 0) return false;
            }
            return true;
        }
        /// <summary>
        /// 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
        /// 有效字符串需满足：左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。注意空字符串可被认为是有效字符串。
        /// </summary>
        /// <param name="s"></param>
        /// <returns></returns>
        public bool IsValid(string s)
        {
            if (string.IsNullOrEmpty(s)) return true;
            Stack<char> stack = new Stack<char>();
            Dictionary<char, int> dic = new Dictionary<char, int>
            {
                { '(',1},
                { '{',2},
                { '[',3},
                { ')',-1},
                { '}',-2},
                { ']',-3},
            };
            foreach (var c in s.ToCharArray())
            {
                if (c == '(' || c == '{' || c == '[') stack.Push(c);
                else
                {
                    if (stack.Count == 0) return false;

                    var temp = stack.Pop();
                    if (dic[c] + dic[temp] != 0)
                    {
                        return false;
                    }
                }
            }

            return stack.Count == 0;
        }

        /// <summary>
        /// 给定一个平衡括号字符串 S，按下述规则计算该字符串的分数：
        /// () 得 1 分。
        /// AB 得 A + B 分，其中 A 和 B 是平衡括号字符串。
        /// (A) 得 2 * A 分，其中 A 是平衡括号字符串。
        /// </summary>
        /// <param name="S"></param>
        /// <returns></returns>
        public int ScoreOfParentheses(string S)
        {
            if (string.IsNullOrEmpty(S)) return 0;
            int n = 0;
            int ans = 0;
            for (int i = 0; i < S.Length; i++)
            {
                var current = S.Substring(i, 1);
                if (current == "(")
                {
                    n++;
                }
                else
                {
                    n--;
                    if (i - 1 >= 0 && S.Substring(i - 1, 1) == "(")
                    {
                        ans += (int)Math.Pow(2, n);
                    }
                }
            }
            return ans;
        }
        /// <summary>
        /// 给定一个只包含三种字符的字符串：（ ，） 和 *，写一个函数来检验这个字符串是否为有效字符串。
        /// 有效字符串具有如下规则：任何左括号(必须有相应的右括号 )。任何右括号 ) 
        /// 必须有相应的左括号( 。左括号 (必须在对应的右括号之前 )。
        /// * 可以被视为单个右括号 ) ，或单个左括号( ，或一个空字符串。一个空字符串也被视为有效字符串。
        /// </summary>
        /// <param name="s"></param>
        /// <returns></returns>
        //public bool CheckValidString(string s)
        //{
        //    if (string.IsNullOrEmpty(s)) return true;
        //}


        /*
         * 给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：
                "123"
                "132"
                "213"
                "231"
                "312"
                "321"
                给定 n 和 k，返回第 k 个排列。

                来源：力扣（LeetCode）
                链接：https://leetcode-cn.com/problems/permutation-sequence
                著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
         * */
        public string GetPermutation(int n, int k)
        {
            //可以组合的个数列表
            int[] factorial = new int[n];
            factorial[0] = 1;
            for (int i = 1; i < n; i++)
            {
                factorial[i] = factorial[i - 1] * i;
            }
            int[] array = new int[n];
            for (int i = 0; i < n; i++)
            {
                array[i] = i + 1;
            }
            StringBuilder ans = new StringBuilder();
            for (int i = 0; i < n; i++)
            {
                int x = ResortPermutation(array, i, k, factorial);
                k -= x;
                if (k <= 0)
                {
                    break;
                }
            }
            for (int i = 0; i < array.Length; i++)
            {
                ans.Append(array[i]);
            }
            return ans.ToString();
        }
        /// <summary>
        /// 重排数组startIndex位置数字
        /// </summary>
        /// <param name="array">数组</param>
        /// <param name="startIndex">startIndex</param>
        /// <param name="k">第k个排列</param>
        /// <param name="factorial">标记组合次数</param>
        private int ResortPermutation(int[] array, int startIndex, int k, int[] factorial)
        {
            //已消耗排列数
            int x = 0;
            if (k <= 0) return x;
            //从startIndex后面的的数字个数
            int remainingItems = array.Length - startIndex - 1;
            //标记首字位下移
            int i = startIndex;
            //队列数量
            int currentCount = factorial[remainingItems];
            //可变化的队列大于k时或者下移到尽头
            if (currentCount < k && i < array.Length)
            {
                do
                {
                    i++;
                    x += factorial[remainingItems];
                    currentCount += factorial[remainingItems];
                } while (currentCount < k && i < array.Length - 1);
            }

            //将第i个item移植startIndex,startindex和i之间的都右移动一位
            int temp = array[i];
            for (int m = i - 1; m >= startIndex; m--)
            {
                array[m + 1] = array[m];
            }
            array[startIndex] = temp;
            return x;
        }

        /// <summary>
        /// 给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
        /// 输入: nums = [1,1,1,2,2,3], k = 2 
        /// 输出: [1,2]
        /// </summary>
        /// <param name="nums"></param>
        /// <param name="k"></param>
        /// <returns></returns>
        public int[] TopKFrequent(int[] nums, int k)
        {
            Dictionary<int, int> index_d = new Dictionary<int, int>();
            Dictionary<int, IList<int>> count_d = new Dictionary<int, IList<int>>();

            for (int i = 0; i < nums.Length; i++)
            {
                if (index_d.ContainsKey(nums[i]))
                {
                    var index = index_d[nums[i]];
                    //+1
                    if (!count_d.ContainsKey(index + 1))
                    {
                        count_d[index + 1] = new List<int>();
                    }
                    count_d[index + 1].Add(nums[i]);
                    //remove old,index change
                    index_d[nums[i]] = index + 1;
                    count_d[index].Remove(nums[i]);
                }
                else
                {
                    index_d[nums[i]] = 1;
                    if (!count_d.ContainsKey(1))
                    {
                        count_d[1] = new List<int>();
                    }
                    count_d[1].Add(nums[i]);
                }
            }

            List<int> result = new List<int>();

            int s = k;
            while (s > 0)
            {
                var max = count_d.Keys.Last();
                result.AddRange(count_d[max]);
                s -= count_d[max].Count;
                count_d.Remove(max);
            }
            return result.ToArray();
        }
        /// <summary>
        /// 1190. 反转每对括号间的子串
        /// 给出一个字符串 s（仅含有小写英文字母和括号）。
        /// 请你按照从括号内到外的顺序，逐层反转每对匹配括号中的字符串，并返回最终的结果。
        /// 注意，您的结果中 不应 包含任何括号。
        /// 输入：s = "(abcd)" 输出："dcba"
        /// 输入：s = "(ed(et(oc))el)" 输出："leetcode"
        /// 输入：s = "a(bcdefghijkl(mno)p)q" 输出："apmnolkjihgfedcbq"
        /// </summary>
        /// <param name="s"></param>
        /// <returns></returns>
        public string ReverseParentheses(string s)
        {
            Stack<string> stack = new Stack<string>();
            StringBuilder sb = new StringBuilder();
            foreach (char ch in s)
            {
                if (ch == '(')
                {
                    stack.Push(sb.ToString());
                    sb.Length = 0;
                }
                else if (ch == ')')
                {
                    char[] arr = sb.ToString().ToCharArray();
                    sb.Length = 0;
                    for (int i = arr.Length - 1; i >= 0; i--)
                    {
                        sb.Append(arr[i]);
                    }
                    sb.Insert(0, stack.Pop());
                }
                else
                {
                    sb.Append(ch);
                }
            }
            return sb.ToString();
        }
    }
}
